1. Field of the Invention
The present invention relates to an encoder that encodes information using a low-density parity-check (LDPC) code and a decoder that decodes the encoded information using the LDPC code. More specifically, the present invention relates to an encoder that encodes information using an array code and a decoder that decodes the encoded information.
2. Description of the Related Art
Low-density parity-check (LDPC) codes are attracting attention as error correction technology. The LDPC code is advantageous in that it is a linear code having fewer “1”s in a check matrix. Because the code length is higher and the codes have randomness, the LDPC code has significantly higher error correction ability than the conventional code. With the LDPC code it is possible to efficiently decode a code sequence using an iterative decoding method called a Sum-Product decoding method.
The LDPC code is applied to detect errors in magnetic disk devices. An LDPC code that can be used to detect errors in magnetic disk devices need to have, for example, satisfactory waterfall characteristic, low error floor, short parity length, high encoding rate, short code length, and it should be a systematic code. Moreover, circuit scales of an encoder and a decoder should be small. An LDPC code that can fulfill all of these requirements has yet to be developed.
The systematic code is a code generated by generating a parity sequence from an information sequence and adding the parity sequence to the information sequence. FIG. 6 is a diagram for explaining the systematic code.
As shown in FIG. 6, this systematic code is a code for generating a code sequence by adding a parity sequence, a parity length of which is M, to an information sequence, an information length of which is K. A code length of the code sequence is N (N=K+M).
FIG. 7 is a diagram of a functional constitution of an encoding/decoding section of a magnetic disk device that uses the conventional LDPC code system. As shown in FIG. 7, this encoding/decoding section includes an LDPC encoder 1, a Partial Response (PR) channel 2, a channel A Posteriori Probability (APP) decoder 3, an LDPC decoder 4, and a threshold judging unit 5.
The LDPC encoder 1 is an encoder that encodes an inputted information sequence uk into an LDPC code sequence xk. The PR channel 2 is a channel that records the LDPC code sequence xk encoded by the LDPC encoder 1 in a magnetic disk according to a partial response system, reproduces information yk recorded in the magnetic disk, and outputs the information yk reproduced to the channel APP decoder 3.
The channel APP decoder 3 is a decoder that applies Maximum Likelihood (ML) decoding to the information yk received from the PR channel 2 and outputs external information Λe (xk′) with respect to the LDPC code sequence xk to the LDPC decoder 4 as a logarithmic likelihood ratio.
The LDPC decoder 4 is a decoder that performs reliability propagation operation with the external information Λe(Xk′) as a priori likelihood, updates the external information Λe(xk′) with respect to the LDPC code sequence Xk, and calculates a posteriori probability Λ(uk′) of an estimated value uk′ with respect to the information sequence uk based on the e xternal information Λe(Xk′).
This LDPC decoder 4 outputs the external information Λe (xk′) updated to the channel APP decoder 3 such that the external information Λe (xk′) is used as a priori information. The LDPC decoder 4 repeats the processing a predetermined number of times and, then, outputs information on the a posteriori probability Λ(uk′) to the threshold judging unit 5.
The threshold value judging unit 5 can obtain the estimated value uk′ with respect to the information sequence uk by acquiring the information on the a posterior probability Λ(uk′) from the LDPC decoder 4 and performing threshold judgment for the a posteriori probability Λ(uk′).
The LDPC code is a linear block code and defined by a check matrix H. FIG. 8 is a diagram of an example of the check matrix H. When the code length is N and the parity length is M, the check matrix H has M rows and N columns.
The check matrix H and a code matrix x are related as follows:HxT=0where x is an N-dimensional vector, 0 is an N-dimensional zero vector, and T represents transposition of x.
When the code sequence x is generated from the information sequence u, a generator matrix G described below is used:x=uGwhere the information sequence u is a K-dimensional vector and the generator matrix G is a matrix with K rows and N columns.
The generator matrix G has a relation described below with the information sequence u, the code sequence x, and the check matrix H.HGT=0where 0 is a zero matrix with M rows and K columns.
If the check matrix H and the generator matrix G are held in a memory in a Large Scale Integration (LSI) included in a hard disk device, the circuit scale of the LSI becomes large. Therefore, examinations have been performed to make it possible to easily hold structures of these matrixes in the LSI or easily generate these matrixes.
For example, as a method of structuring the check matrix H, there is a method that uses an array code. In an array-LDPC code obtained by applying the array code to the LDPC code, the check matrix H is structured using a cyclic permutation matrix (see, for example, John L. Fan, “Array Codes as Low-Density Parity-Check Codes”, in Proc. 2nd. Int. Symp. Turbo Codes, Brest, France, September 2000, pp. 543-546).
An example of the check matrix H of the array-LDPC code is shown below:
          ⁢      H    =          [                                    I                                I                                I                                ⋯                                I                                                I                                σ                                              σ              2                                            ⋯                                              σ                              k                -                1                                                                          I                                              σ              2                                                          σ              4                                            ⋯                                              σ                              2                ⁢                                  (                                      k                    -                    1                                    )                                                                                          ⋮                                ⋮                                ⋮                                ⋰                                ⋮                                                I                                              σ                              j                -                1                                                                        σ                              2                ⁢                                  (                                      j                    -                    1                                    )                                                                          ⋯                                              σ                                                (                                      j                    -                    1                                    )                                ⁢                                  (                                      k                    -                    1                                    )                                                                        ]      where I is a unit matrix with p rows and p columns (p is a prime number: p=1, 3, 5, 7, 11, . . . ). j and k are a column weight and a row weight ofthe check matrix H, respectively, and satisfy a relation of j, k≦p.
σ is a cyclic permutation matrix with p rows and p columns obtained by moving “1”s of the unit matrix I in a row or column direction. An example of σ is shown below:
  σ  =      [                            0                          1                          0                          0                          0                                      0                          0                          1                          0                          0                                      0                          0                          0                          1                          0                                      0                          0                          0                          0                          1                                      1                          0                          0                          0                          0                      ]  
The array-LDPC code has a characteristic that there is no cycle, length of which is 4, in a Tanner graph and it is possible to prevent deterioration in decoding performance and structure the check matrix H. However, the generator matrix G has a disadvantage that, in general, the generator matrix G does not have a specific structure.
Therefore, a method of recursively performing encoding of an information sequence using a structured check matrix has also been proposed. However, computational complexity at the time of encoding increases (see, for example, U.S. Pat. No. 6,895,547 specification).
An Irregular Repeat-Accumulate (IRA)-LDPC code that holds down computational complexity at the time of encoding and realizes a low error floor has also been proposed (see, for example, M. Yang, W. E. Ryan, and Y. Li, “Design of efficiently encodable moderate-length high-rate irregular LDPC codes,” IEEE Trans. Comm., Vol. 52, No. 4, pp. 564-571, April 2004).
In this IRA-LDPC code, the check matrix H with M rows and N columns is divided into a square matrix H2 with M rows and M columns and a matrix H1 with the remaining M rows and K columns (K=N−M).H=[H1H2]
In this case, the generator matrix G is represented as follows.G=[I(H2−1H1)T]
In the IRA-LDPC code, the check matrix H1 is a matrix generated at random (a random interleaver) and the check matrix H2 has a structure of 1+D (D means delay of 1) represented as follows.
      H    2    =      [                            1                          0                          0                          0                          0                          0                                      1                          1                          0                          0                          0                          0                                      0                          1                          1                          0                          0                          0                                      0                          0                          1                          1                          0                          0                                      0                          0                          0                          1                          1                          0                                      0                          0                          0                          0                          1                          1                      ]  where, “+” is an exclusive OR operator.
FIG. 9 is a diagram for explaining an encoder that performs the conventional IRA-LDPC encoding. As shown in FIG. 9, this encoder multiplies the information sequence u by a check matrix H1T and applies a transfer function 1/(1+D) to an output of the multiplication to thereby generate a parity sequence p from the information sequence u.
However, if the conventional IRA-LDPC code is applied to an apparatus that permits intersymbol interference, like a magnetic disk device using the partial response system, if there is a portion where “1” continues in the check matrix H, error rate characteristic is not satisfactory.
Specifically, a column weight of the check matrix H2 in the IRA-LDPC code is 2. When there is intersymbol interference, error propagation among bits tends to occur and a decline in error correction ability is inevitable. It is generally known that the LDPC code, a column weight of which is 2, is poor in error floor characteristic.
Therefore, there is a need of a technology that can control deterioration in error rate characteristic, reduce computational complexity related to encoding and decoding, and reduce circuit scales of an encoding circuit and a decoding circuit while structuring a check matrix.